package top.codetheory;

// 按两次 Shift 打开“随处搜索”对话框并输入 `show whitespaces`，
// 然后按 Enter 键。现在，您可以在代码中看到空格字符。
public class Main {
    public static void main(String[] args) {
        System.out.println(fib1(35));
        System.out.println(fib2(35));
        System.out.println(fib(35));
    }

    public static int fib(int n) {
        if (n <= 1) {
            return n;
        }
        return fib(n-1) + fib(n-2);
    }

    public static int fib1(int n) {
        if (n <= 1) {
            return n;
        }
        int left = 0, right = 1;
        for (int i = 0; i < n - 1; i++) {
            int sum = left + right;
            left = right;
            right = sum;
        }
        return right;
    }
    public static int fib2(int n) {
        if (n <= 1) {
            return n;
        }
        int left = 0, right = 1;
        while (n-- > 1) {
            right += left;
            left = right - left;
        }
        return right;
    }
}